Modular computations in a finite field, or Galois field, are denoted as GF(2.sup.n). Modular operations on GF(2.sup.n) are used in cryptography for various applications, such as authentication of messages, identification of a user, and exchange of keys. Exemplary applications are described in the French Patent Application No. 2 679 054.
Integrated circuits dedicated to such applications are commercially available. For example, one such integrated circuit is manufactured by SGS-THOMSON MICROELECTRONICS S.A. and is built around a central processing unit and an arithmetic coprocessor. This product has a reference designation of ST16CF54 and is dedicated to the performance of modular computations. The coprocessor enables the processing of modular operations using the Montgomery method. Further information on this coprocessor can be found in European Patent Application No. 0 601 907 A2. FIG. 1 shows a modular arithmetic coprocessor according to the prior art. This figure corresponds to FIG. 2 of the European application.
The basic operation of modular computations according to the Montgomery method is known as the P.sub.field method. In this method, three binary data elements A (multiplicand), 13 (multiplier) and N (modulo) are encoded on an integer number of n bits which is used to produce a binary data element referenced as P(A, B).sub.N. This binary data element is encoded on n bits such that P(A, B).sub.N =A*B*I mod N, where I is an error due to the Montgomery method. The Montgomery method uses a k-bit computation base and analyzes the n-bit words into m words of k bits, such that m*k&gt;n&gt;(m-1)* k. The Montgomery method operates as follows, with i being an index varying from 0 to m-1:
X=S.sub.i +A.sub.i *B; PA1 Y.sub.0 =(X*J.sub.0) mod 2.sup.k ; PA1 Z=X+(N*Y.sub.0); PA1 S.sub.i+1 =Z.backslash.2.sup.k, .backslash. being an integer division; PA1 if S.sub.i+1 is greater than N, then N is subtracted from S.sub.i+1 at the next iteration; PA1 A.sub.i corresponds to a k-bit word of the binary date element A; PA1 S.sub.i corresponds to an updated result of the P.sub.field operation; and PA1 S.sub.m =P(A, B).sub.N =A*B*I mod N.
To obtain a modular multiplication A*B mod N, it is necessary to eliminate the error I. Error I is known and equals 2.sup.-m*k. To eliminate the error I, a second P.sub.field operation is performed: P(S.sub.m, H).sub.N, where H is a binary data element encoded on m words of k bits and equals 2.sup.2m*k mod N. The generation of a parameter H can be done by successive subtractions by a computation coprocessor such as the one described in the European application. It is also possible to combine successive subtractions and P.sub.field operations to compute H as disclosed in the European Patent Application EP-A-0 712 070.
When modular multiplications are performed with data elements of variable size, the value of H may assume different values as a function of the sizes of A, B and N. In general, H has the value 2.sup.x mod N, with x and N being non-zero integers. This is explained in the European Patent Application EP-A-712 071.
Furthermore, the coprocessor is also used to perform computations on operands with sizes greater than the maximum size of the registers of the coprocessors. The European Patent Document EP-A-0 785 502 discloses a successive subtraction circuit for processing values of N having a size twice that of the registers of the coprocessor.